#include <vector>
#include <map>
#include <algorithm>
using namespace std;

// 这种写法相比双指针更直观，但时间复杂度略高，为 O(n^2 log n)（因为 map 的插入和查找是 O(log n)）。
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& num) {
        vector<vector<int>> res;
        sort(num.begin(), num.end());
        int n = num.size();

        for (int i = 0; i < n; i++) {
            // 去重：跳过相同的 num[i]
            if (i > 0 && num[i] == num[i - 1]) continue;

            int target = -num[i];
            map<int, int> mp;  // 记录已访问的数
            for (int j = i + 1; j < n; j++) {
                int need = target - num[j];
                if (mp.count(need)) {
                    vector<int> triplet = {num[i], need, num[j]};
                    sort(triplet.begin(), triplet.end());
                    res.push_back(triplet);

                    // 跳过重复 num[j]
                    while (j + 1 < n && num[j] == num[j + 1]) j++;
                }
                mp[num[j]] = j;
            }
        }

        // 去重：三元组可能重复（如不同 i 导致相同组合）
        sort(res.begin(), res.end());
        res.erase(unique(res.begin(), res.end()), res.end());

        return res;
    }
};
